#!/bin/sh
#
# Copyright (c) 2007-2008 The PureDarwin Project.
# All rights reserved.
#
# @LICENSE_HEADER_START@
#
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions
# are met:
# 1. Redistributions of source code must retain the above copyright
#    notice, this list of conditions and the following disclaimer.
# 2. Redistributions in binary form must reproduce the above copyright
#    notice, this list of conditions and the following disclaimer in the
#    documentation and/or other materials provided with the distribution.
#
# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
# IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
# THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
# PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR
# CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
# EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
# PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
# PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
# LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
# NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
# SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
#
# @LICENSE_HEADER_END@
#

#
# aladin <aladin@puredarwin.org>
#

#
# Generate a DOT file, a dependencies tree of one or more given KEXTs
# based on pd_portviz
#
# 	Usage: pd_kextviz KernelExtension.kext [...]
#

#
# Changelog
#
# 20081209 - License header update - aladin
# 20081017 - Many fixes - aladin 
# 20081014 - Initial release - aladin 
#

# Initialization
echo $1 | grep '^[0-9]$' > /dev/null
if [ $? -eq 0 ]; then
	# Recursive level count found in arg1
	LEVEL=$1
	# Eating arg1
	shift
else
	#
	# Preventive tests
	#

	# Ensure root exclusivity
	if [ "$UID" -ne 0 ]; then
		echo "$(tput bold)Aborting!$(tput reset) You must be root in order to run \`$(basename $0)'"
		exit 1
	fi

	# Ensure graphviz is available
	if [ ! -x /opt/local/bin/dot ]; then
		echo "$(tput bold)Warning!$(tput reset) /opt/local/bin/dot is not executable"
		echo "You should install \`graphviz' port for graphic output"
	fi

	# Ensure at least one KEXT is given
	if [ "$1" == "" ]; then
		echo "Usage: $(basename $0) KernelExtension.kext [...]"
		exit 1
	fi

	if [ $# -gt 1 ]; then
		# Global var sux
		export OUTPUT_FILENAME=SLE.dot 
		KEXTS="$*"
	else
		export OUTPUT_FILENAME=$(basename "$1").dot
		KEXTS="$1"
	fi

	echo
	echo "Generate dependencies graphs of $*"
	echo

	# DOT begin
	echo "digraph untitled {" > "$OUTPUT_FILENAME"

	# Do not draw the legend by default
	IS_LEGEND="false"
	if [ "$IS_LEGEND" == "true" ]; then
		# DOT Legend
		cat >>"$OUTPUT_FILENAME"<<EOOF
  		subgraph clusterLegend { 

 			<KEXT>          [shape=none, style="rounded,filled", fillcolor="#9999FFCF"];
			<No dependency> [shape=none, style="rounded,filled", fillcolor="#CCCCFFCF"];

			<KEXT> -> <No dependency>; 
			<KEXT> -> <KEXT> [label=" blocker", headclip=false, fontcolor=red,color=red, style=bold]; 
			<No dependency> -> <No dependency>  [label=" symbols missing", fontcolor=gray, color=gray]; 

			label="Legend of KEXT dependencies." 
		}  
EOOF
	fi
	
	# CLI legend
	echo " Legend:"
	echo " 1\t + foo ()"
	echo " 2\t |\`- bar (bundle id)                                 No more dependency"
	echo " 2\t |\`+ baz $(tput bold)impure!$(tput reset) /Blocker_1 -> file_involved_1       Impurity detected"
	echo " 2\t |\`+ baz $(tput bold)impure!$(tput reset) /Blocker_. -> file_involved_.       Impurity detected"
	echo " 2\t |\`+ baz $(tput bold)impure!$(tput reset) /Blocker_n -> file_involved_n       Impurity detected"
	echo " 2\t |\`+ qux ()                                          Dependency found"
	echo " 3\t | |\`. bar (cached: bundle id)                       Cached bundle identifier"
	echo " 1\t . qux                                               Cached kext (Already processed)"
	
        echo 
        echo "Now generating dependencies tree, please wait..."
        echo 

	KEXTS_COUNT=0
	for KEXT in $KEXTS; do
		# Ensure KEXT existence (because of space in filename, mainly..)
		if [ -e "$KEXT" ]; then
			KEXTS_COUNT=$[$KEXTS_COUNT + 1] 
			# Recursive call
			$0 1 $KEXT
		fi
	done

	# DOT end
	echo "} " >> "$OUTPUT_FILENAME"

	echo "$KEXTS_COUNT kexts parsed"

	if [ $KEXTS_COUNT -gt 0 ]; then
		echo "Generation of $OUTPUT_FILENAME $(tput bold)complete$(tput reset)."
		echo	
		echo "Now drawing graphs from $OUTPUT_FILENAME, please wait..."
		
		OUTPUT_FORMAT="png"

		/opt/local/bin/dot   -T$OUTPUT_FORMAT -o "${OUTPUT_FILENAME}_directed.$OUTPUT_FORMAT"     "$OUTPUT_FILENAME"
		echo "Generation of ${OUTPUT_FILENAME}_directed.${OUTPUT_FORMAT} $(tput bold)complete$(tput reset)."

		/opt/local/bin/circo -T$OUTPUT_FORMAT -o "${OUTPUT_FILENAME}_circular.$OUTPUT_FORMAT"     "$OUTPUT_FILENAME"
		echo "Generation of ${OUTPUT_FILENAME}_circular.${OUTPUT_FORMAT} $(tput bold)complete$(tput reset)."
	       
		/opt/local/bin/twopi -T$OUTPUT_FORMAT -o "${OUTPUT_FILENAME}_radial.$OUTPUT_FORMAT"        "$OUTPUT_FILENAME"
		echo "Generation of ${OUTPUT_FILENAME}_radial.${OUTPUT_FORMAT} $(tput bold)complete$(tput reset)."
	       
		/opt/local/bin/neato -T$OUTPUT_FORMAT -o "${OUTPUT_FILENAME}_undirected.$OUTPUT_FORMAT"    "$OUTPUT_FILENAME"
		echo "Generation of ${OUTPUT_FILENAME}_undirected.${OUTPUT_FORMAT} $(tput bold)complete$(tput reset)."
	       
		/opt/local/bin/fdp   -T$OUTPUT_FORMAT -o "${OUTPUT_FILENAME}_undirectedBIS.$OUTPUT_FORMAT" "$OUTPUT_FILENAME"
		echo "Generation of ${OUTPUT_FILENAME}_undirectedBIS.${OUTPUT_FORMAT} $(tput bold)complete$(tput reset)."
	fi
	exit 0
fi

#
# Variables
#

KEXT=$1
T_KEXT_DEPENDENCY=$2

# Simple blacklist based on https://sites.google.com/a/puredarwin.org/puredarwin/developers/macports/purity
KEXT_BLOCKERS="
/AppKit.framework
/ApplicationServices.framework
/Carbon.framework
/Cocoa.framework
/CoreServices.framework
/Foundation.framework
/Symbolication.framework
"

# Cosmectic padding
TEXT_PADDING=""
for ((x=1;  x <= $[$LEVEL - 1] ; x++))  
do
 	 TEXT_PADDING="$TEXT_PADDING |"
done

if [ $LEVEL -gt 1 ]; then
	TEXT_PADDING=" $LEVEL\t$TEXT_PADDING\`+"
else	
	TEXT_PADDING=" $LEVEL\t$TEXT_PADDING +"
fi

# KEXT already processed?
#
#	The dot file is used as a simple cache
grep "	<$KEXT> \[label=\"$(basename "$KEXT")\", shape=none, style=\"rounded,filled\", fillcolor=\"#9999FFCF\"\];" "$OUTPUT_FILENAME" > /dev/null
if [ ! $? -eq 0 ]; then
	KEXT_FILES=`find "$KEXT" -name '*'`
	KEXT_BLOCKER_COUNT=0
	# inspecting all the mach-o files of the portname
	for KEXT_OBJECT_FILE in "$KEXT_FILES"; do
		# otool map the object file?
		KEXT_OBJECT_FILE_SHARED_LIBS=`/usr/bin/otool -L "$KEXT_OBJECT_FILE" 2> /dev/null`
		if [ $? -eq 0 ]; then
			# is the file an object file? (Because otool return 0 even if it is or if it is not an object file)
			echo $KEXT_OBJECT_FILE_SHARED_LIBS | grep "is not an object file" > /dev/null
			if [ ! $? -eq 0 ]; then
				# looking for current blocker(s)
				for KEXT_BLOCKER in $KEXT_BLOCKERS; do
					echo $KEXT_OBJECT_FILE_SHARED_LIBS | grep "$KEXT_BLOCKER" > /dev/null
					if [ $? -eq 0 ]; then
						echo "$TEXT_PADDING $KEXT $(tput bold)impure!$(tput reset) $KEXT_BLOCKER -> $KEXT_OBJECT_FILE"
						KEXT_BLOCKER_COUNT=$[$KEXT_BLOCKER_COUNT + 1]
					fi
				done
			fi
		fi
	done
	if [ $KEXT_BLOCKER_COUNT -gt 0 ]; then
		echo "	<$KEXT> -> <$KEXT> [label=\" x$KEXT_BLOCKER_COUNT \", headclip=false, fontcolor=red, color=red, style=bold];" >> "$OUTPUT_FILENAME"
	fi

	# Dependency found?
	KEXT_DEPENDENCIES=`kextlibs "$KEXT" 2> /dev/null` # Bundle identifier
	RET=$?

	# From `man kextlibs'
	# 
	#       0 on completion if all undefined symbols are found exactly once
	#       1 if any undefined symbols remain
	#       2 if any symbols are found in more than one library kext
	#       3 Can't open executable for x.kext  (not in the man)
	case "$RET" in
	1)
		echo "	<$KEXT> -> <$KEXT> [label=\" $(kextlibs $KEXT 2>&1 1>/dev/null | sed 's/ symbols not found in any library kext//')\", fontcolor=gray, color=gray];" >> "$OUTPUT_FILENAME"
		;;
	*)
		;;
	esac

	if [ "$KEXT_DEPENDENCIES" != "" ]; then
		echo "	<$KEXT> [label=\"$(basename "$KEXT")\", shape=none, style=\"rounded,filled\", fillcolor=\"#9999FFCF\"];" >> "$OUTPUT_FILENAME"
		echo "$TEXT_PADDING $KEXT ($T_KEXT_DEPENDENCY)"
		
		# Iterative loop against Bundle identifier
		for KEXT_DEPENDENCY in `echo "$KEXT_DEPENDENCIES" | awk -F "=" {'print $1'}`; do
			# Bundle_id -> KEXTdependency already resolved?
			grep "##	<$KEXT_DEPENDENCY> -> <" "$OUTPUT_FILENAME" > /dev/null
			if [ ! $? -eq 0 ]; then
				KEXT_DEPENDENTS=`kextfind -bundle-id -substring "$KEXT_DEPENDENCY" -print`
				for KEXT_DEPENDENT in $KEXT_DEPENDENTS; do
					# Recursive call on each run time dependency with its bundle id
					$0 $[$LEVEL + 1] $KEXT_DEPENDENT $KEXT_DEPENDENCY

					# Used as bundle cache + resolv
					echo "##	<$KEXT_DEPENDENCY> -> <$KEXT_DEPENDENT>;" >> "$OUTPUT_FILENAME"
					echo "	<$KEXT> -> <$KEXT_DEPENDENT>;" >> "$OUTPUT_FILENAME"
				done
			# Bundler_id -> KEXTdependency already resolved
			else
				# cache inside
				T_KEXT_DEPENDENT=`grep "$KEXT_DEPENDENCY" "$OUTPUT_FILENAME" | sort | uniq | awk -F "-> " {'print $2'} | awk -F ";" {'print $1'}`
				echo "	<$KEXT> -> $T_KEXT_DEPENDENT;" >> "$OUTPUT_FILENAME"
				echo "$TEXT_PADDING\b\b |\`. $T_KEXT_DEPENDENT (cached: $KEXT_DEPENDENCY)"
			fi
		done
	# No dependency found
	else
		echo "	<$KEXT> [label=\"$(basename "$KEXT")\", shape=none, style=\"rounded,filled\", fillcolor=\"#CCCCFFCF\"];" >> "$OUTPUT_FILENAME"
		echo "$TEXT_PADDING\b- $KEXT ($T_KEXT_DEPENDENCY)"
	fi
# KEXT has already been processed	
else
	echo "$TEXT_PADDING\b. $KEXT"
fi

